package com.linzm.leetcode.mid.tree.递归遍历;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author zimingl
 * @Date 2023/2/22 22:52
 * @Description: 1 确定递归函数的参数和返回值 2 确定终止条件 3 确定单层递归的逻辑  利用了系统栈
 * 递归 系统栈
 * 迭代 栈
 * Morris遍历
 */
public class Demo {
    public static void main(String[] args) {
        Demo demo = new Demo();
        List<Integer> list = demo.traversal(TreeNode.getTree());
        System.out.println(list);
    }

    private List<Integer> traversal(TreeNode treeNode) {
        List<Integer> list = new ArrayList<>();
        preOrder(list, treeNode);
        return list;
    }

    private void preOrder(List<Integer> list, TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        list.add(treeNode.val);
        preOrder(list, treeNode.left);
        preOrder(list, treeNode.right);
    }

    private void inOrder(List<Integer> list, TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        inOrder(list, treeNode.left);
        list.add(treeNode.val);
        inOrder(list, treeNode.right);
    }

    private void postOrder(List<Integer> list, TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        postOrder(list, treeNode.left);
        postOrder(list, treeNode.right);
        list.add(treeNode.val);
    }
}
